<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Maximum Sub Square Matrix Dynamic Programming</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="maximum-sub-square-matrix-dynamic-programming">Maximum Sub Square Matrix Dynamic Programming</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=_Lf1looyJMU&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=27">https://www.youtube.com/watch?v=_Lf1looyJMU&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=27</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/MaximumSizeSubMatrix.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/MaximumSizeSubMatrix.java</a></li>
</ul>
<p>用python写的话，会简单很多</p>
<pre><code class="language-java"><div>    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> <span class="hljs-title">min</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a,<span class="hljs-keyword">int</span> b, <span class="hljs-keyword">int</span> c)</span></span>{
        <span class="hljs-keyword">int</span> l = Math.min(a, b);
        <span class="hljs-keyword">return</span> Math.min(l, c);
    }
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">maxSize</span><span class="hljs-params">(<span class="hljs-keyword">int</span> arr[][])</span></span>{
        
        <span class="hljs-keyword">int</span> result[][] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[arr.length][arr[<span class="hljs-number">0</span>].length];
        <span class="hljs-keyword">int</span> max = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i &lt; arr.length; i++){
            result[i][<span class="hljs-number">0</span>] = arr[i][<span class="hljs-number">0</span>];
            <span class="hljs-keyword">if</span> (result[i][<span class="hljs-number">0</span>] == <span class="hljs-number">1</span>)
            {
                max = <span class="hljs-number">1</span>;
            }
        }
        
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i &lt; arr[<span class="hljs-number">0</span>].length; i++){
            result[<span class="hljs-number">0</span>][i] = arr[<span class="hljs-number">0</span>][i];
            <span class="hljs-keyword">if</span> (result[<span class="hljs-number">0</span>][i] == <span class="hljs-number">1</span>)
            {
                max = <span class="hljs-number">1</span>;
            }
            
        }
        
        
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>; i &lt; arr.length; i++){
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j=<span class="hljs-number">1</span>; j &lt; arr[i].length; j++){
                <span class="hljs-keyword">if</span>(arr[i][j] == <span class="hljs-number">0</span>){
                    <span class="hljs-keyword">continue</span>;
                }
                <span class="hljs-keyword">int</span> t = min(result[i-<span class="hljs-number">1</span>][j],result[i-<span class="hljs-number">1</span>][j-<span class="hljs-number">1</span>],result[i][j-<span class="hljs-number">1</span>]);
                result[i][j] =  t +<span class="hljs-number">1</span>;
                <span class="hljs-keyword">if</span>(result[i][j] &gt; max){
                    max = result[i][j];
                }
            }
        }
        <span class="hljs-keyword">return</span> max;
    }
</div></code></pre>

    </body>
    </html>